package _go

/*40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。



示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]*/

var res [][]int

func combinationSum2(candidates []int, target int) [][]int {
	res = [][]int{}

	n := len(candidates)
	if n == 0 {
		return res
	}
	//先做个排序 这样可以方便去重
	sort.Ints(candidates)
	dfs(candidates, target, 0, []int{})
	return res
}

//参数定义与前一个一样
func dfs(candidates []int, target, index int, path []int) {
	if target == 0 {
		tmp := make([]int, len(path))
		copy(tmp, path)
		res = append(res, tmp)
		return
	}

	for i := index; i < len(candidates); i++ {
		if target-candidates[i] < 0 {
			continue
		}
		//重点在此   可以去掉已经选择过的切重复的选择
		if i > index && candidates[i] == candidates[i-1] {
			continue
		}
		v := candidates[i]
		path = append(path, candidates[i])
		dfs(candidates, target-v, i+1, path)
		path = path[:len(path)-1]
	}
}
